/*
 * @lc app=leetcode.cn id=273 lang=cpp
 *
 * [273] 整数转换英文表示
 */

// @lc code=start
class Solution {
public:
    string w0_19[20] = {"#", "One", "Two", "Three", "Four",
                    "Five", "Six", "Seven", "Eight", "Nine",
                    "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen",
                    "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    string w20_100[10] = {"#", "#", "Twenty", "Thirty", "Forty", "Fifty",
                    "Sixty", "Seventy", "Eighty", "Ninety"};
    string w1000[3] = {"Billion", "Million", "Thousand"};
    
    string w0_99(int x){
        string res;
        if(x >= 100){
            res += w0_19[x / 100] + " Hundred ";
            x %= 100;
        }
        if(x >= 20){
            res += w20_100[x / 10] + " ";
            x %= 10;
            if(x) res += w0_19[x] + " ";
        }
        else if(x)
            res += w0_19[x] + " ";
        
        return res;
    }
    string numberToWords(int num) {
        //每三位是一个轮回
        //重点在于0-999的一个实现
        if(num == 0) return "Zero";
        string ans;
        for(int i = 1e9, j = 0; i > 1; i /= 1000, j++){
            if(num / i){
                ans += w0_99(num / i) + w1000[j] + " ";
            }
            num = num % i;
        }
        if(num) ans += w0_99(num);
        ans.pop_back();
        return ans;
    }
};
// @lc code=end

